#! /usr/bin/env python3

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 0123456 -> 4560123
        if nums == []:
            return -1

        def get_shift_point():
            low, high = 0, len(nums) - 1
            mid = 0
            while nums[low] > nums[high]:
                mid = (low + high) // 2
                if nums[mid] >= nums[low]:
                    low = mid + 1
                elif nums[mid] < nums[high]:
                    high = mid - 1
            if nums[mid] > nums[mid - 1]:
                return mid
            else:
                return mid - 1

        def helper(start, end):
            while start <= end:
                mid = (start + end) // 2
                if nums[mid] == target:
                    return mid
                elif nums[mid] > target:
                    end = mid - 1
                else:
                    start = mid + 1
            return -1

        mid = get_shift_point()
        if mid == -1:
            mid = len(nums) - 1
        if nums[0] > target:
            return helper(mid + 1, len(nums) - 1)
        else:
            return helper(0, mid)


if __name__ == "__main__":
    s = Solution()
    nums = list(range(10))
    for i in range(10):
        tmp = nums[i:] + nums[:i]
        a = s.search(tmp, 100)
        print(tmp, tmp[a], a)
